In this paper we initiate a study of distributed deterministic broadcastingin ad-hoc wireless networks with uniform transmission powers under the SINRmodel. We design algorithms in two settings: with and without local knowledgeabout immediate neighborhood. In the former setting, our solution has almostoptimal O(Dlog2 n) time cost, where n is the size of a network, D is theeccentricity of the network and {1,...,N} is the set of possible node IDs. Inthe latter case, we prove an Omega(n log N) lower bound and develop analgorithm matching this formula, where n is the number of network nodes. As oneof the conclusions, we derive that the inherited cost of broadcastingtechniques in wireless networks is much smaller, by factor aroundmin{n/D,Delta}, than the cost of learning the immediate neighborhood. Finally,we develop a O(D Delta log2 N) algorithm for the setting without localknowledge, where Delta is the upper bound on the degree of the communicationgraph of a network. This algorithm is close to a lower bound Omega(D Delta).
展开▼
